package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class FindGreatestSumOfSubArray {

  @Test
  public void test() {
    System.out.println(FindGreatestSumOfSubArray(new int[] {6, -3, -2, 7, -15, 1, 2, 2}));
    System.out.println(FindGreatestSumOfSubArray(new int[] {6, -3, -2}));
    System.out.println(FindGreatestSumOfSubArray(new int[] {-3, -2}));
  }

  public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length == 0) {
      return 0;
    }

    int max = array[0];
    int sum = 0;
    for (int a : array) {
      if (sum + a > a) {
        sum += a;
      } else {
        sum = a;
      }

      if (sum > max) {
        max = sum;
      }
    }

    return max;
  }
}
